package com.wingsfrog.puzzle.util;

import com.wingsfrog.puzzle.service.PuzzlesService;
import org.springframework.beans.factory.annotation.Autowired;

import javax.transaction.Transactional;
import java.util.*;

public class PuzzleUtil {
    private final static int[] directionArr = {-3, -1, 1, 3}; // 分别是上左右下
    public enum DIRECTION {
        UP((byte)0, -3), DOWN((byte)1, 3), LEFT((byte)2, -1), RIGHT((byte)3, 1); // 不要改这里
        private Byte id;
        private Integer delta;

        private DIRECTION(Byte id, int delta) {
            this.id = id;
            this.delta = delta;
        }

        public Byte getId() {
            return id;
        }

        public void setId(Byte id) {
            this.id = id;
        }

        public Integer getDelta() {
            return delta;
        }

        public void setDelta(Integer delta) {
            this.delta = delta;
        }
    }

    public static long hashGridAndStart(int[] _grids, int start) { // 计算九宫格的hash
        long num = start;
        for (int i = 0; i < 9; i++) {
            long l = _grids[i];
            num = num | (l << (4 + 4 * i));
        }
        return num;
    }

    public static long hashGrid(int[] _grids) { // 计算九宫格的hash
        long num = 0;
        for (int i = 0; i < 9; i++) {
            long l = _grids[i];
            num = num | (l << (4 * i));
        }
        return num;
    }

    private static int[] dehashGrid(long hash) {
        int[] grids = new int[9];
        for (int i = 0; i < 9; i++) {
            grids[i] = (int) (hash & 15);
            hash /= 16;
        }
        return grids;
    }

    private static int disarrange(int[] _grids, int i, int start) {
        Random random = new Random();
        int[] grids = _grids.clone();
        List<Long> gridList = new ArrayList<>();
        while (i > 0) {
            int direction = directionArr[random.nextInt(4)];
            if (cantGo(direction, start)) continue;
            int newPos = start + direction;

            int[] tmpArr = grids.clone();
            tmpArr[start] = grids[newPos];
            tmpArr[newPos] = grids[start];

            // 检查目前的局面之前是否已经遇到过
            long hash = hashGrid(tmpArr);
            if (gridList.contains(hash)) continue;
            else gridList.add(hash);
            grids = tmpArr;

            start = newPos;
            --i;
        }
        System.out.print('[');
        for (int i1 = 0; i1 < grids.length; i1++) {
            _grids[i1] = grids[i1];
            System.out.print(grids[i1]);
            System.out.print(',');
        }
        System.out.print("], ");
        System.out.println(start);
        try {
            Solver solver = new Solver();
            solver.solve(grids, start);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return start;
    }

    public static void disarrange(long hash, List<Map<String, String>> list) {
        int[] arr = dehashGrid(hash);
        List<Map<String, String>> tmpList = new ArrayList<>(list);
        for (int j = 0; j < arr.length; j++) {
            int newPos = arr[j];
            if (newPos != j)
                list.set(j, tmpList.get(newPos));
        }
    }

    private static boolean cantGo(int direction, int start) { // 边界检测
        switch(direction) {
            case -3: // 上
                return start / 3 == 0;
            case -1: // 左
                return start % 3 == 0;
            case 1: // 右
                return start % 3 == 2;
            case 3: // 下
                return start / 3 == 2;
        }
        return false; // 永远不应该走到这个return
    }

    public static boolean canGo(DIRECTION dir, int start) {
        return dir == DIRECTION.UP && (start / 3 > 0)
                || dir == DIRECTION.DOWN && (start / 3 < 2)
                || dir == DIRECTION.LEFT && (start % 3 > 0)
                || dir == DIRECTION.RIGHT && (start % 3 < 2);
    }

    public static class State {
        public int[] grids;
        public int xPos;
        public long hash; // grids的哈希值
        public long stateHash; // State的哈希值
        public List<DIRECTION> step;

        public State(int[] grids, int xPos, List<DIRECTION> step) {
            this.grids = grids;
            this.xPos = xPos;
            this.hash = hashGrid(grids);
            this.stateHash = hashGridAndStart(grids, xPos);
            this.step = step;
        }
    }

    public static class Solver {
        private Map<Long, List<DIRECTION>> ansCache = new HashMap<>();

        private boolean notDone(int[] _grids) { // 检查九宫格是否已经处于完成状态
            for (int i = 0; i < 9; i++) {
                if (_grids[i] != i) return true;
            }
            return false;
        }

        private int[] exchange(int[] grid, int pos1, int pos2) {
            int[] newGrid = grid.clone();
            newGrid[pos1] = grid[pos2];
            newGrid[pos2] = grid[pos1];
            return newGrid;
        }

        private State go(int[] grid, DIRECTION dir, int pos, List<DIRECTION> step) {
            int newPos = 0;
            List<DIRECTION> newStep = new ArrayList<>(step);
            switch(dir) {
                case UP:
                    if (pos / 3 == 0) return null;
                    newPos = pos - 3;
                    newStep.add(DIRECTION.UP);
                    break;
                case DOWN:
                    if (pos / 3 == 2) return null;
                    newPos = pos + 3;
                    newStep.add(DIRECTION.DOWN);
                    break;
                case LEFT:
                    if (pos % 3 == 0) return null;
                    newPos = pos - 1;
                    newStep.add(DIRECTION.LEFT);
                    break;
                case RIGHT:
                    if (pos % 3 == 2) return null;
                    newPos = pos + 1;
                    newStep.add(DIRECTION.RIGHT);
                    break;
            }
            return new State(exchange(grid, pos, newPos), newPos, newStep);
        }

        public List<DIRECTION> solve(long hash, int start) {
            int[] grids = dehashGrid(hash);
            return solve(grids, start);
        }

        public List<DIRECTION> solve(int[] grids, int start) {
            assert grids.length == 9;

            List<State> stateList = new ArrayList<>();
            State originState = new State(grids, start, new ArrayList<>());
            stateList.add(originState);

            List<Long> visited = new ArrayList<>();
            visited.add(originState.hash); // 记录访问过的九宫格

            List<DIRECTION> answer = null; // 记录找出的最佳答案

            while(stateList.size() > 0) {
                State state = stateList.get(0);
                stateList.remove(0);
                if (ansCache.containsKey(state.stateHash)) { // 构造答案
                    List<DIRECTION> newDir = new ArrayList<>();
                    List<DIRECTION> nextDir = ansCache.get(state.stateHash);
                    newDir.addAll(state.step);
                    newDir.addAll(nextDir);
                    if (answer == null || answer.size() > newDir.size()) answer = newDir;
                } else if (notDone(state.grids)) {
                    for (DIRECTION direction : DIRECTION.values()) {
                        State newState = go(state.grids, direction, state.xPos, state.step);
                        if (newState != null) {
                            if (answer != null && newState.step.size() >= answer.size())
                                continue; // 如果目前答案的步数超过这个步数的话，就不用继续找下去了
                            if (!visited.contains(newState.hash)) {
                                visited.add(newState.hash);
                                stateList.add(newState);
                            }
                        }
                    }
                } else {
                    if (answer == null || answer.size() > state.step.size()) answer = state.step;
                    else if (answer.size() > state.step.size()) answer = state.step;
                    if (answer.size() == 1) {
                        break;
                    }
                }
            }
            ansCache.put(originState.stateHash, answer);
            return answer;
        }
    }

}
